import java.util.*;

public class SpiralOrder {

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int total = rows * cols;

        int top = 0, bottom = rows - 1;
        int left = 0, right = cols - 1;

        while (res.size() < total) {
            for (int col = left; col <= right && res.size() < total; col++) {
                res.add(matrix[top][col]);
            }
            top++;

            for (int row = top; row <= bottom && res.size() < total; row++) {
                res.add(matrix[row][right]);
            }
            right--;

            if (top <= bottom) {
                for (int col = right; col >= left && res.size() < total; col--) {
                    res.add(matrix[bottom][col]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int row = bottom; row >= top && res.size() < total; row--) {
                    res.add(matrix[row][left]);
                }
                left++;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        System.out.println(spiralOrder(matrix));
    }
}
